package com.whitedust.top80;

/**
 *
 * @author A
 * @since 2025/11/15 23:30
 */

public class Top78 {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int edge = 0;
        //dp[i][j]表示以matrix[i-1][j-1]为正方形右下角的正方形最大边长为多少
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    //如果这个点能作为正方形右下角，则左上，左边，上边均要为正方形对应的右下角
                    dp[i + 1][j + 1] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
                    edge = Math.max(edge, dp[i + 1][j + 1]);
                }
            }
        }
        return edge * edge;
    }
}
